package club.xiaojiawei.array;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 2022/4/21 0:32
 * @question 76.最小覆盖数
 * @description 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 * <br><strong>注意：</strong>
 * 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
 * 如果 s 中存在这样的子串，我们保证它是唯一的答案。
 */
public class MinCoverSubstring76 {
    public static void main(String[] args) {
        String s = "aabccccabcb", t = "ac";
        System.out.println(minWindow(s, t));
        System.out.println(minWindow2(s, t));
    }

    /**
     * 滑动窗口法
     * @param s
     * @param t
     * @return
     */
    public static String minWindow(String s, String t) {
        String[] targetString = new String[s.length()];
        int[] targetIndex = new int[s.length()];
        int sIndex = 0, iIndex = 0;
        String temp;
        int amount = 0;
        for (int i = 0; i < s.length(); i++) {
            temp = s.substring(i, i + 1);
            if (t.contains(temp)){
                targetString[sIndex++] = temp;
                targetIndex[iIndex++] = i;
                amount++;
            }
        }
        HashMap<String, Integer> map = new HashMap<>();
        Integer tempI;
        String tempS;
        for (int i = 0; i < t.length(); i++) {
            if ((tempI = map.get(tempS = t.substring(i, i+1))) == null){
                map.put(tempS, 1);
            }else {
                map.put(tempS, tempI+1);
            }
        }
        int tempStart = 0, tempEnd = -1, start = 0, end = -1, e;
        Integer tempCount;
        String tempStr;
        int h = 0;
        for (int i = 0; i < amount; i++) {
            if ((tempCount = map.get(targetString[i])) == 1){
                map.put(targetString[i], 0);
                end = tempEnd = i;
            }else if (tempCount > 1){
                map.put(targetString[i], tempCount - 1);
                end = tempEnd = i;
            }else {
                e = i;
                while (e > -1 && tempStart < amount ){
                    if ((tempStr = targetString[tempStart]).equals(targetString[e]) && map.get(tempStr) + h <= 0){
                        tempStart++;
                        e--;
                        tempEnd = i;
                        h = 1;
                        if ((tempCount = map.get(tempStr)) < 0){
                            map.put(tempStr, tempCount + 1);
                        }
                    }else if ((tempCount = map.get(tempStr)) < 0){
                        tempStart++;
                        map.put(tempStr, tempCount + 1);
                    }else if (tempEnd != i){
                        map.put(targetString[i],map.get(targetString[i]) - 1);
                        break;
                    }else {
                        break;
                    }
                }
                h = 0;
            }
            if (targetIndex[tempEnd] - targetIndex[tempStart] < targetIndex[end] - targetIndex[start]){
                end = tempEnd;
                start = tempStart;
            }

        }
        if (end - start + 1< t.length()){
            return "";
        }else {
            return s.substring(targetIndex[start], targetIndex[end] + 1);
        }
    }

    /**
     * 滑动窗口法-民间
     * @param s
     * @param t
     * @return
     */
    public static String minWindow1(String s, String t) {
        int slen=s.length();
        int tlen=t.length();
        if(slen<tlen){return "";}
        int[] need=new int[128];
        for(int i=0;i<tlen;i++){
            need[t.charAt(i)]++;
        }
        int l=0,r=0,count=tlen,size=Integer.MAX_VALUE,start=0;
        while(r<slen){
            char c=s.charAt(r);
            if(need[c]>0){
                count--;
            }
            need[c]--;
            if(count==0){
                while(l<r&&need[s.charAt(l)]<0){
                    need[s.charAt(l)]++;
                    l++;
                }
                if(r-l+1<size){
                    size=r-l+1;
                    start=l;
                }
                need[s.charAt(l)]++;
                l++;
                count++;
            }
            r++;
        }
        return size==Integer.MAX_VALUE?"":s.substring(start,start+size);
    }

    /**
     * 滑动窗口法-民间，优化
     * @param s
     * @param t
     * @return
     */
    @SuppressWarnings("all")
    public static String minWindow2(String s, String t) {
        int[] tInt = new int[128];
        int tLen = t.length();
        int sLen = s.length();
        for (int i = 0; i < tLen; i++) {
            tInt[t.charAt(i)]++;
        }
        int l = 0, r = 0, count = tLen, start = 0, size = Integer.MAX_VALUE;
        char temp;
        while (r < sLen){
            if (tInt[temp = s.charAt(r)] > 0){
                count--;
            }
            tInt[temp]--;
            if (count == 0){
                while (l < r && tInt[temp = s.charAt(l)] < 0){
                    l++;
                    tInt[temp]++;
                }
                if (r - l + 1< size){
                    size = r - l + 1;
                    start = l;
                }
                count++;
                l++;
                tInt[temp]++;
            }
            r++;
        }
        return size == Integer.MAX_VALUE? "" : s.substring(start, start + size);
    }
}
